package algorithm.bitcalculate;

/**
 * <pre>
 *有n双筷子摆在你的面前。已知长度相等的两根筷子可以配对，输出无法配对的那一根筷子的长度。
输入样例：
5
1 1 2 2 2
输出样例：
2
数据范围：
100%的数据：n<2×10^7，n为奇数，每根筷子的长度小于2^31。数据保证有且只有一根筷子无法配对。

思路：只是让人找到无法匹配的筷子的长度，所以如果能够直接算出来不就ok了。将每个数字用二进制表示，
纵向比较n个数同个位置的0,1情况，由于只有一双筷子无法匹配，故而0的个数和1的个数一定相差1。再考虑到如果1的个数是偶数，那么0就是奇数个，
反之，1奇数个，0偶数个。所以用 异或运算，可以直接计算这个位置是0还是1
 * </pre>
 * </p>
 * (可填，此类型设计的详细描述).
 *
 * @see (可填，引用或参考其他类型资源，如: {@link java.util.Properties}).
 * @author zhangbo
 * @since 1.0.0
 */
public class Chopsticks {
    public int match(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }

    public void execute() {
        int[] nums = { 1, 1, 1000, 3, 45, 5, 6, 45, 6, 5, 3 };
        System.out.println(match(nums));
    }

    public static void main(String[] args) {
        Chopsticks run = new Chopsticks();
        run.execute();
    }
}
